package 每日一题;

import java.util.Arrays;

public class 最长子序列的个数 {

    public int findNumberOfLIS(int[] nums) {
        if (nums.length==0)
            return 0;
        int[] dp = new int[nums.length];
        int[] ints = new int[nums.length];
        int max=1;
        int res=0;
        Arrays.fill(dp,1);
        Arrays.fill(ints,1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i]>nums[j]){
                    if (dp[i]<dp[j]+1){
                        dp[i]=dp[j]+1;
                        ints[i]=ints[j];
                    }
                    //找到新路
                    else if (dp[i]==dp[j]+1) {
                        ints[i] += ints[j];
                    }
                }
            }
            max=Math.max(max,dp[i]);
        }
        for (int i = 0; i < nums.length; i++) {
            if (dp[i]==max){
                res+=ints[i];
            }
        }
        return res;
    }
}
